package com.gthncz;

import java.util.Scanner;
import java.util.ArrayDeque;
import java.util.Deque;
public class Main4 {

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(){}
        public TreeNode(int val){
            this.val = val;
            left = right = null;
        }
    }


    private void levelTranverse2(TreeNode root){
        if (root == null) return;
        Deque<TreeNode>[] stack = new Deque[2];
        stack[0] = new ArrayDeque<TreeNode>();
        stack[1] = new ArrayDeque<TreeNode>();

        // 指示当前栈和下一个栈
        int current = 0;
        int next = 1;

        stack[current].push(root);
        while (!stack[0].isEmpty() || !stack[1].isEmpty()){
            if ((current & 0x01) == 0){
                // 当前是奇数层, root开始
                while (!stack[current].isEmpty()){
                    TreeNode node = stack[current].peek();
                    stack[current].pop();
                    System.out.printf("%d ", node.val);
                    if (node.left != null) stack[next].push(node.left);
                    if (node.right != null) stack[next].push(node.right);
                }
            } else {
                // 当前是偶数层
                while (!stack[current].isEmpty()){
                    TreeNode node = stack[current].peek();
                    stack[current].pop();
                    System.out.printf("%d ", node.val);
                    if (node.right != null) stack[next].push(node.right);
                    if (node.left != null) stack[next].push(node.left);
                }
            }
            current = next;
            next = 1 - next;
        }

    }


    // 层序遍历
    private void levelTranverse(TreeNode root){
        if (root == null) return;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            while (size-- > 0){
                TreeNode node = queue.poll();
                System.out.printf("%d ", node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        Main4 main = new Main4();
        main.levelTranverse(root);

    }
}